package com.ssh;

import java.util.ArrayList;
import java.util.List;

public class SolveNQueens_51 {
	public static void main(String[] args) {
		System.out.println(solveNQueens(5));
	}
	public static List<List<String>> solveNQueens(int n) {
		if (n < 0) {
			return null;
		}
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < n; i++) {
			sb.append(".");
		}
		String[] s = new String[n];
		for (int i = 0; i < n; i++) {
			sb.setCharAt(i,'Q');
			s[i] = sb.toString();
			sb.setCharAt(i, '.');
		}
		List<List<String>> list = new ArrayList<List<String>>();
		l(list,new ArrayList<>(),s);
        return list;
    }
	
	private static void l (List<List<String>> list, List<String> l, String[] s) {
		if (l.size() == s.length) {
			list.add(new ArrayList<>(l));
		}
		for (int i = 0; i < s.length; i++) {
			if (l.contains(s[i])) {
				continue;
			}
			boolean x = false;
			for (int j = l.size()-1,a=i-1,b=i+1; j >= 0 ; j--,a--,b++) {
				if (a>=0 && l.get(j).equals(s[a])) {
					x = true;;
					break; 
				}
				if (b<s.length && l.get(j).equals(s[b])) {
					x = true;
					break; 
				}
			}
			if (x) continue;
			
			l.add(s[i]);
			l(list,l,s);
			l.remove(s[i]);
		}
	}
}
